教育部重点实验室专题报告：解决1

报告题目：解决1-线最小线段斯坦纳树问题的近似算法

报告人：李建平教授，云南大学

报告时间：2023年12月15日16:00

报告地点：行健楼学术活动室503

Abstract：In this talk, we address the $1$-line minimum Steiner tree of line segments (1L-MStT-LS) problem. Specifically, given a set $S$ of $n$ disjoint line segments in $\mathbb{R}^2$, we are asked to find the location of a line $l$ and a set $E_l$ of necessary line segments in $\mathbb{R}^2$ such that a graph consisting of all line segments in $S\cup E_l$ plus this line $l$, simply denoted by $T_l=(S, l, E_l)$, becomes a Steiner tree, the objective is to minimize total weight of line segments ({\it i.e.}, edges) in $E_l$ among all such Steiner trees mentioned-above, {\it i.e.}, $\min\{\sum_{e\in E_l} w(e)$ $\vert $ $T_l=(S, l, E_l)$ is a tree mentioned-above$\}$, where weight $w(e)$ is the Euclidean distance between the two endpoints of that segment $e\in E_l$. For convenience, we refer to such a tree $T_l$ as a $1$-line (minimum) Steiner tree of line segments. Similarly, we are asked to find a set $E_0$ of necessary line segments in $\mathbb{R}^2$ such that a graph only consisting of all line segments in $S\cup E_0$, simply denoted by $T_S=(S,E_0)$, becomes a Steiner tree in $\mathbb{R}^2$, the objective is to minimize total weight of line segments ({\it i.e.}, edges) in $E_0$ among all such Steiner trees mentioned-above, we refer to this problem as the minimum Steiner tree of line segments (MStT-LS) problem. In addition, when two endpoints of each line segment in $E_0$ needs to be located on two different line segments in $S$, respectively, we refer to that problem as the minimum spanning tree of line segments (MST-LS) problem. Furthermore, when each line segment in $S$ degenerates to be a point, the MStT-LS problem becomes the Euclidean minimum Steiner tree problem.

We obtain three main results. (1) Using techniques of computational geometry to construct a Voronoi diagram of line segments, we design an exact algorithm in time $O(n\log n)$ to solve the MST-LS problem; (2) we show that the algorithm designed in (1) is a $1.214$-approximation algorithm to solve the MStT-LS problem; (3) using the combination of the algorithm designed in (1) as a subroutine for many times, a technique of finding linear facility location and a key lemma proved by techniques of computational geometry, we present a $1.214$-approximation algorithm in time $O(n^3\log n)$ to solve the 1L-MStT-LS problem.

Keywords: 1-line minimum Steiner tree of line segments; minimum spanning tree of line segments; Voronoi diagram of line segments; Steiner ratio; approximation algorithms

报告人简介：

李建平，1983年9月至1988年7月，就读于中国科学技术大学数学系，应用数学专业，获理学学士学位；1988年9月至1991年2月，就读于中国科学院系统科学研究所，运筹学与控制论专业，获理学硕士学位；1996年12月至1999年10月，就读于法国巴黎南大学，计算机科学专业，获博士学位。作为博士后在加拿大麦克马斯特（McMaster）大学计算机科学系工作，作为研究员在香港城市大学计算机科学系工作，作为教授/访问学者先后访问过香港大学、台湾中研院数学所、普林顿大学、西弗吉尼亚大学、佐治亚理工学院和加州大学欧文分校等。

研究领域：组合优化、离散数学及理论计算机科学。

1991年3月至今，就职于云南大学数学系，2000年8月获得教授职位，2005年8月获得指导博士研究生导师资格，2010年5月获得教授二级岗位，2022年1月至今获云南大学特岗骨干教授岗位。入选云南省“兴滇英才支持计划”云岭学者（2019年10月），云南省首届“百名海外高层次人才引进计划” （2011年5月）；获云南省中青年学术技术带头人称号（2011年12月），云南省自然科学奖励（2011年、2018年），云南省有突出贡献优秀专业技术人才奖励（2012年），云南省高等学校教学名师奖（2010年5月），全国宝钢优秀教师奖（2020年5月）。指导博士研究生17人，硕士研究生若干人。

从2003年1月至今，主持国家自然科学基金项目8项，发表科研论文过100篇；作为学术带头人，领导云南大学数学团队获“云南省运筹学创新团队”称号和“云南省高校计算理论与应用科技创新团队” 称号；现任中国工业与应用数学学会图论组合及应用分会副主任委员，中国运筹学会理事，中国运筹学会图论组合分会常务理事，云南省数学类教学指导委员会主任委员。